Data communication systems are used to exchange information between devices. The information to be exchanged comprises data that is organized as strings of digital bits formatted so as to be recognizable by other devices and to permit the information to be processed and/or recovered.
The exchange of information may occur over a publically accessible network, such as a communication link between two devices, over a dedicated network within an organization, or may be between two devices within the same dedicated component, such as within a computer or point of sale device.
The devices may range from relatively large computer systems through to telecommunication devices, cellular phones, monitoring devices, sensors, electronic wallets and smart cards, and a wide variety of devices that are connected to transfer data between two or more of such devices.
A large number of communication protocols have been developed to allow the exchange of data between different devices. The communication protocols permit the exchange of data in a robust manner, often with error correction and error detection functionality, and for the data to be directed to the intended recipient and recovered for further use.
Because the data may be accessible to other devices, it is vulnerable to interception and observation or manipulation. The sensitive nature of the information requires that steps are taken to secure the information and ensure its integrity.
A number of techniques collectively referred to as cryptographic encryption protocols, key agreement protocols, and authentication protocols have been developed to provide the required attributes and ensure security and/or integrity in the exchange of information. These techniques utilize a key that is combined with the data. An extensive survey of cryptography techniques is provided in Menezes, van Oorshot and Vanstone's Handbook of Applied Cryptography, the contents of which are incorporated by reference.
There are two main types of cryptosystems, symmetric key cryptosystems and asymmetric or public key cryptosystems. In a symmetric key cryptosystem, the devices exchanging information share a common key that is known only to the devices intended to share the information. Symmetric key systems have the advantage that they are relatively fast and therefore able to process large quantities of data in a relatively short time, even with limited computing power. However, the keys must be distributed in a secure manner to the different devices, which leads to increased overhead and vulnerability if the key is compromised.
Asymmetric or public key cryptosystems utilize a key pair, one of which is public and the other private, associated with each device. The public key and private key are related by a “hard” mathematical problem so that even if the public key and the underlying problem are known, the private key cannot be recovered in a feasible time. One such problem is the factoring of the product of two large primes, as utilized in RSA cryptosystems. Another is the discrete log problem in a finite group. A generator, α, of the underlying group is identified as a system parameter and a random integer, k, generated for use as a private key. To obtain a public key, K, a k-fold group operation is performed so that K=f(α,k).
Different groups may be used in discrete log cryptosystems including the multiplicative group of a finite field, the group of integers in a finite cyclic group of order p, usually denoted Zp* and consisting of the integers 0 to p−1. The group operation is generally an operation such that αk=f(α,k).
Another group that is used for enhanced security is an elliptic curve group. The elliptic curve group consists of elements, represented by pairs of field elements, one of which is designated x and the other y, that satisfy the equation of the chosen elliptic curve. For an elliptic curve group over field of size p, the elliptic curve would generally be defined by the relationship y2 mod p=x3+ax+b mod p. Other curves are used for different groups, as is well known. Each such pair of elements is a point on the curve. P is an element on the elliptic curve group of a large order. The group operation is addition, so a private key k will have a corresponding public key kP=f(α,k).
Public key cryptosystems reduce the infrastructure necessary with symmetric key cryptosystems. A device may generate an integer k, and generate the corresponding public key kP. The public key is published so it is available to other devices. The device may then use a suitable signature protocol to sign a message using the private key k and other devices can confirm the integrity of the message using the public key kP.
Similarly, a device may encrypt a message to be sent to another device using the other devices public key. The message can then be recovered by the other device using the private key. However, these protocols are computationally intensive, and therefore relatively slow, compared with symmetric cryptosystem protocols.
Public key cryptosystems may also be used to establish a key that is shared between two devices. In its simplest form, as proposed by Diffie-Hellman, each device sends a public key to the other device. Both devices then combine the received public key with their private key to obtain a shared key.
One device, usually referred to as an entity (or correspondent), Alice, generates a private key ka and sends another device, or entity, Bob, the public key kaP.
Bob generates a private key kb and sends Alice the public key kbP
Alice computes ka·kbP and Bob computes kb·kaP so they share a common key K=kakbP=kbkaP. The shared key may then be used in a symmetric key protocol. Neither Alice nor Bob may recover the private key of the other, and third parties cannot reconstruct the shared key.
However, in the foreseeable future, conventional cryptography schemes may be compromised due to the emergence of quantum computing. Many practitioners skilled in the art believe that in less than a handful of decades, quantum computing will have widespread use. The emergence of quantum computers provides an evolutionary leap in computation power. However, adversaries or interlopers looking to intercept the encrypted communication may also gain access to the power of quantum computing to break encryption and gain access to supposedly secured communications. One of the important abilities of quantum computers is to efficiently, which means in polynomial time, factor large integers and solve the discrete logarithm problem (for example, given g and h=gx in group G, find x). A significant factor affecting cryptography's security is based on these two mathematical problems, which are considered to be safe in the realm of classical computing. This means that with the appearance of quantum computers, classical cryptosystems may no longer be safe. The field of ‘post-quantum cryptography’ is involved in developing cryptosystems for classical computers so that the classical computer systems would be quantum-resistant and secure against possible adversaries employing quantum computing.
With respect to key agreement protocols for existing post-quantum cryptographic schemes, including elliptic curve cryptography, the key agreements have usability issues due to the manner in which they are required to be used.
It is therefore an object of the present invention to provide a cryptographic scheme in which the above disadvantages are obviated or mitigated and attainment of the desirable attributes is facilitated.